package com.ujs.listnode.code.ReverseList;

import com.ujs.listnode.code.ListNode;
import com.ujs.listnode.code.NodeInit;
import com.ujs.listnode.code.RemoveNode.RemoveElements;

import java.util.ArrayList;
import java.util.List;

/**
 * 206. 反转链表
 * https://leetcode.cn/problems/reverse-linked-list/description/
 *
 * @author zhangshihao
 * @create 2023-09-27 15:00
 */
public class reverseList {
    public static void main(String[] args) {
        ListNode head = NodeInit.getNode();
        ListNode listNode = reverseList3(head);
        while (listNode != null) {
            System.out.print(listNode.getVal() + " ");
            listNode = listNode.getNext();
        }
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        List<Integer> valList = new ArrayList<>();
        while (head != null) {
            valList.add(head.val);
            head = head.next;
        }
        ListNode newHead = new ListNode(valList.get(valList.size() - 1));
        ListNode pre = newHead;
        for (int i = valList.size() - 2; i >= 0; i--) {
            pre.next = new ListNode(valList.get(i));
            pre = pre.next;
        }
        return newHead;
    }

    /**
     * 双指针法
     *
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre; // 改变指针的指向
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public static ListNode reverseList3(ListNode head) {
        return reverse(null, head);
    }


    public static ListNode reverse(ListNode pre, ListNode cur) {
        if (cur == null) return pre;
        ListNode temp = cur.next;
        cur.next = pre; // 改变指针的指向
        return reverse(cur, temp);
    }
}
